// 中序遍历的顺序是左子树 -> 根节点 -> 右子树
// 实现思路
// 节点有左子树：
// 如果目标节点有左子树，那么它的前一个节点就是其左子树中最右边的节点。
// 节点没有左子树：
// 若目标节点没有左子树，需要向上回溯其父节点。如果该节点是其父节点的右子节点，那么其父节点就是前一个节点；若该节点是其父节点的左子节点，则需要继续向上回溯，直到找到一个节点是其父节点的右子节点，或者回溯到根节点。


// 定义二叉树节点类
class TreeNode {
    constructor(val = 0, left = null, right = null, parent = null) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.parent = parent;
    }
}

function findPrevNode(node) {
    // 情况 1: 节点有左子树
    if (node.left) {
        let temp = node.left;
        while (temp.right) {
            temp = temp.right;
        }
        return temp;
    }

    // 情况 2: 节点没有左子树
    let parent = node.parent;
    while (parent && node === parent.left) {
        node = parent;
        parent = parent.parent;
    }
    return parent;
}